/*
    created: 2023/4/13
    filename: RPN.c
    author: 李东霖
    purpose: 使用栈将中缀表达式转换为RPN
    思路：怎么转换为逆波兰表达式，一个中缀表达式里面存在运算符，操作数和改变优先级的括号  
    假如存在一个中缀表达式： （（1+5*5）*1）/7-（1+2）*2   155*+1*7/12+2*-
    现在我们对他进行转换 
    ***我们遇到两个(  进栈 （                     此时的栈 （（
    我们遇到1写入到返回字符串中 
    ***我们遇到+  进栈 +                     此时的栈 （（+
    我们遇到5写入到返回字符串 
    ***我们遇到* 与我们的栈顶元素相比，优先级比它高，进栈*  此时的栈 （（+*
    ***我们遇到），开始将出栈元素直到遇到一个（       此时的栈（
    我们遇到5，写入字符串  
    ***我们遇到* 进栈                此时的栈（*
    ***我们遇到），出栈元素直到遇到（     此时的栈 
    ***遇到/ 因为栈里没有东西了，进栈    此时的栈 /
    遇到7，写入到字符串  
    ***遇到-，他的优先级和栈顶元素比低了，所以出栈/继续判断，没有了所以-进栈    此时的栈-
    ............. 不写了，懒
*/
#include"../liststack/liststack.h"
int toRPN(const char* src,char* des)
{
    //测试的str = “（（1+5*5）*1）/7-（1+2）*2” 
    if(src == NULL) return -1;
    PListStack stack = InitStack2();
    if(stack == NULL) return -1;
    ElemType ee;
    int ipos1 = 0;
    int len = strlen(src);
    int ipos2 = 0;
    for(ipos1 = 0 ;ipos1 != len;++ipos1)
    {
        //数字和字母直接追加到后缀表达式后面。
        if (( (src[ipos1]>='0') && (src[ipos1]<='9') ) ||
            ( (src[ipos1]>='a') && (src[ipos1]<='z') ) ||
            ( (src[ipos1]>='A') && (src[ipos1]<='Z') ) )
        {
        des[ipos2]=src[ipos1];
        ipos2++; 
        continue;
        }
        
        //左括号
        if(src[ipos1]=='(')
        {
            Push(stack,&src[ipos1]);
            continue;
        }
        //右括号
        if(src[ipos1]==')')
        {
            while(1)
            {
                if(Pop(stack,&ee) != 1)return 0;
                if(ee == '(') break;
                des[ipos2++]=ee;
            }
            continue;
        }
        //运算符
        if(src[ipos1]=='+'||src[ipos1]=='-'||src[ipos1]=='*'||src[ipos1]=='/')
        {
            while(1)
            {
                //获取栈顶元素，判断优先级  还有空栈的情况
                if(GetTop(stack,&ee) != 1) break;
                //如果是左括号，那么直接进栈
                if(ee == '(') break;
                //优先级判断  
                int pri1;//弹出元素的优先级 
                int pri2;//当前元素的优先级 

                if(src[ipos1]=='+'||src[ipos1]=='-') pri2 = 1;
                if(src[ipos1]=='*'||src[ipos1]=='/') pri2 = 2;
                if(ee=='+'||ee=='-') pri1 = 1;
                if(ee=='*'||ee=='/') pri1 = 2;

                //判断优先级 当前符号优先级大于栈顶元素  进栈
                if(pri1<pri2) break;
                //出栈栈顶元素，继续判断
                else
                {
                    Pop(stack,&ee);
                    des[ipos2++] = ee;
                    continue;
                }
            }
            Push(stack,&src[ipos1]);
            continue;
        }
    }

    //弹出栈的元素，存放到表达式的后面
    while(1)
    {
        if(Pop(stack,&ee) != 1) break;
        des[ipos2++] = ee;
    }
    return 1;
}
int main()
{
    char str1[101],str2[101];  
    memset(str1,0,sizeof(str1));
    memset(str2,0,sizeof(str2));

    printf("请输入待转换的表达式：");
    fgets(str1,100,stdin);     // 不建议用gets函数，gets函数编译时可能会出现警号。
    str1[strlen(str1)-1]=0;    // 删除str1最后的换行。
    printf("输入转换的表达式=%s=\n",str1);

    // 把中缀表达式str1转换为后缀表达式str2。
    if (toRPN(str1,str2) == 0) { printf("转换失败。\n"); return -1; }

    printf("转换成功=%s=。\n",str2);

    return 0;
}